package algorithm_optimal_solution.StackAndQueue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

//栈实现汉诺塔，不能直接从左到右或从右到左。要点在于小压大和相邻不可逆原则。
//非递归核心理论：第一个动作必然为left->mid；如果上一步是left->mid，根据小压大原则这一步必然不会是left->mid，且mid->right与right->mid只会有一个达标，
//根据相邻不可逆原则必然不会是mid->left，所以每一步只有一个选择。
public class StackForHanoi {

    enum Action{
        No,
        LToM("left","mid"),
        MToL("mid","left"),
        RToM("right","mid"),
        MToR("mid","right");

        private String from;
        private String to;

        Action(){}

        Action(String from,String to){
            this.from = from;
            this.to = to;
        }

        public String getFrom(){
            return this.from;
        }

        public String getTo(){
            return this.to;
        }
    }

    public void action(int count){
        Stack<Integer> leftStack = new Stack<>();
        Stack<Integer> midStack = new Stack<>();
        Stack<Integer> rightStack = new Stack<>();
        leftStack.push(Integer.MAX_VALUE);
        midStack.push(Integer.MAX_VALUE);
        rightStack.push(Integer.MAX_VALUE);
        for(int i=count;i>0;i--){
            leftStack.push(i);
        }
        Action[] preAction = { Action.No };
        int steps=0;
        while(rightStack.size() != count+1){
            steps += rules(preAction,Action.MToL,Action.LToM,leftStack,midStack);
            steps += rules(preAction,Action.LToM,Action.MToL,midStack,leftStack);
            steps += rules(preAction,Action.MToR,Action.RToM,rightStack,midStack);
            steps += rules(preAction,Action.RToM,Action.MToR,midStack,rightStack);
        }
        System.out.println("It will move " + steps + " steps.");
    }

    private int rules(Action[] preAction, Action preNoAction, Action nowAction,
                     Stack<Integer> fromStack, Stack<Integer> toStack){
        if(preAction[0] != preNoAction && fromStack.peek() < toStack.peek()){//上一步不能够是相邻不可逆原则的移动方向
            toStack.push(fromStack.pop());
            preAction[0]=nowAction;
            System.out.println("Move " + toStack.peek() + " from " +
                    nowAction.getFrom() + " to " + nowAction.getTo());
            return 1;
        }
        return 0;
    }

    public static void main(String[] args)throws IOException {
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(scanner.readLine());
        new StackForHanoi().action(len);
    }
}
